package nbranch.tree.level.order;

import java.util.LinkedList;
import java.util.List;

import nbranch.tree.perorder.Node;

/**
 * @Date 2020/03/16
 * @author 王光浩 
 * @Thinking 使用递归。
 * @Analysis 时间复杂度O（n），空间复杂度O（n）
 */
public class MyMethodOne {
	public List<List<Integer>> levelOrder(Node root) {
		LinkedList<List<Integer>> res=new LinkedList<List<Integer>>();
		if(root==null)return res;
		List<Integer> first=new LinkedList<Integer>();
		first.add(root.val);
		res.add(first);
		LinkedList<List<Node>> queue=new LinkedList<List<Node>>();
		if(root.children!=null && !root.children.isEmpty())
			queue.add(root.children);
		//进行层序遍历,每一次循环将相应层数的节点加入到res集中
		while(!queue.isEmpty()) {
			int size=queue.size();
			List<Integer> levelInt=new LinkedList<Integer>();
			for(int i=0;i<size;i++) {
				List<Node> node=queue.poll();
				for(Node tem:node) {
					levelInt.add(tem.val);
					if(tem.children!=null && !tem.children.isEmpty())queue.add(tem.children);
				}
			}
			res.add(levelInt);
		}
		return res;
	}
}
